/**
 * @author LKQ
 * @date 2022/1/29 11:38
 * @description 深度优先搜索
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0 ,1}};
        solution.findCircleNum(isConnected);
    }
    public int findCircleNum(int[][] isConnected) {
        int provinces = isConnected.length;
        boolean[] visited = new boolean[provinces];
        int circles = 0;
        for (int i = 0 ; i < provinces; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, provinces, i);
                circles++;
            }
        }
        return circles;
    }
    public void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) {
        for (int j = 0; j < provinces; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                dfs(isConnected, visited, provinces, j);
            }
        }
    }
}
